package sort.merge;

/**
 * 归并排序原理：先拆分，再合并，归并排序首先将序列进行拆分直到每个序列不能拆分为止，
 * 然后对序列进行两两合并(合并的过程需要排序),知道最终只存在一个序列为止
 * <p>
 * 归并排序效率分析：归并排序运行的时间复杂度为O(nlogn) 空间代价为O(n)
 * <p>
 * 最好情况和最差情况下时间复杂度均为O(nlogn),归并排序是一种稳定的外部排序算法
 * <p>
 * 归并排序C 代码递归方式实现(当然可以对其采用迭代方式实现)
 */
public class MergeSort {

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] array = {1, 5, 9, 3, 4, 18, 7, 6};
        mergeSort.print(array);
        System.out.println();
        MergeSort.sort(array, 0, array.length - 1);
        mergeSort.print(array);
    }

    /**
     * 归并排序
     */
    public static void merge(int a[], int low, int mid, int high) {
        int[] temp = new int[high - low + 1];
        int i = low;
        int j = mid + 1;
        int k = 0;
        // 把较小的数先移到新数组中
        while (i <= mid && j <= high) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        // 把左边剩余的数移入数组
        while (i <= mid) {
            temp[k++] = a[i++];
        }
        // 把右边边剩余的数移入数组
        while (j <= high) {
            temp[k++] = a[j++];
        }

        // 把新数组中的数覆盖nums数组
        for (int l = 0; l < temp.length; l++) {
            a[l + low] = temp[l];
        }
    }

    public static void sort(int a[], int low, int high) {
        int mid = (low + high) / 2;
        if (low < high) {
            sort(a, low, mid);
            sort(a, mid + 1, high);
            merge(a, low, mid, high);
        }
    }

    public void print(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + ",");
        }
    }
}
